Data compression is the process of representing a large amount of data with a smaller amount. Data compression is typically used to map a large bandwidth signal into a smaller bandwidth channel for transmission or storage.
One method of data compression that has gained recent interest is vector quantization. Vector quantization has been found to afford a higher compression ratio without sacrificing significant signal quality to the degree required by other known data compression methods.
Vector quantization lends itself particularly well to audio or video signals that will be interpreted by human listeners and viewers. Human interpreted data require less accuracy than does machine interpreted data. For example, the data needed to store and identically reproduce a color video image displayed on a conventional television monitor, can be compressed significantly without losing the essence of the main image that the human viewer would discern.
To compress a signal by vector quantization, the signal, if not in digital form, is converted to a set of digital data elements and the digital data elements of the set grouped in some manner into blocks referred to as signal vectors. Signal vectors can be any N by M group of digitized data elements derived from the original signal, with N and M being any integer value.
Vector quantization further requires a collection of "code words", sometimes referred to as a "code book". Code words are representative vectors which are equal in size to the signal vectors being compressed. The code words are used to approximate the signal vectors generated from the original signal when the compressed representation of the original signal is decompressed. Typically, these representative vectors or code words are generated using a probability density function to identify the most commonly occurring signal vectors in the type of signals being compressed.
In vector quantization, each code word in the code book is assigned a unique associated binary code. The code has fewer binary bits than the code word itself and fewer binary bits than any signal vector represented by the code word. The smaller in size the code is with respect to the size of the signal vector, or, more accurately, the digital data used to generate the signal vector, the greater the compression that is achieved Typically, the code words of the code book would be stored in a random access memory for quick retrieval. The code uniquely associated with each code word can then be related to the unique address of the code word in the memory.
After creating a code book of code words, each of the signal vectors generated from a signal to be compressed is compared with the code words to find one code word that best represents the signal vector. This generally means finding a code word having minimal distortion with respect to the signal vector.
Originally, two main approaches were followed for comparing signal vectors with code words to determine minimal distortion: sequential search through the entire code book or tree structured search through part of the code book. Vector quantization by either approach is disclosed in detail, for example, in U.S. Pat. No. 4,560,977 to Murakami, et.al., incorporated by reference in its entirety herein.
Related patent U.S. Pat. No. 4,979,039 filed Jan. 30, 1989, discloses a third approach, more powerful in practice than either sequential or tree structured searching, namely hashing. Hashing represents the antithesis of an ordered search. Hashing, as it relates to practical vector quantization, involves the creation of a function which, when exercised on a signal vector, identifies one of at least three different subsets of code words in the set of code words within which a close approximation of the signal vector will be found. The signal vector is then compared with only the code words of the one identified subset and is replaced with the code of the code word of the identified subset having the least distortion with respect to the hashed signal vector.
The present invention is related to improvements in methods and apparatus for vector quantization by hashing.